The present invention relates to layout compaction method and apparatus for a leaf cell of an LSI, such as a standard cell and a cell for a data path module, for use in an LSI such as a CMOS LSI.
Recent development of automated manufacturing system for semiconductor LSIs has provided system designers with freedom in selecting a manufacturing foundry, namely, a system designer or a design vendor can select a manufacturing foundry which provides a process technique with highest performance at a lowest cost on the basis of common design data. Accordingly, a difference in the process techniques between the foundries is directly linked with an order-receiving competition for LSIs, and hence the open competition in the process techniques has become more and more intensified.
Such an intensified competition in the process techniques accelerates the development of the process techniques, and in addition, high performance system design can be developed aiming at a process technique which is being put to practical use in the near future. Moreover, design rules have been more and more complicated since the start of a deep-submicron age, so that the necessary number of design rules was approximately 30 five year ago but now is 100 or more, and each of such many rules affects the manufacturing cost and yield. Therefore, it has become more and more difficult to determine design rules at an initial stage of the manufacture. These facts affect the development of a leaf cell of an LSI such as a standard cell and a cell for a data path module as follows:
1) As a result of intensified change of the process techniques, a frequency of designing cell libraries is remarkably increased. Five years ago, one series of libraries is developed per two years, but recently the frequency is increased so that one series of libraries is developed per half a year. In addition, the number of cells included in each library has substantially doubled as compared with that of five years ago.
2) In order to develop and provide a cell in a short period of time, it is necessary to start cell design before defining design rules and ultimately modify the layout when the design rules are defined at the final stage.
3) Abstraction in the design has been shifted from a mask layout and circuit design toward system design, and hence, the number of engineers for the mask layout and the circuit design has been greatly decreased.
Accordingly, techniques of cell synthesis and cell compaction has been regarded largely significant. Moreover, since the area of a leaf cell directly affects not only the area of a chip but also a cost of the chip, the cell area is required to be integrated similarly to or more highly than that attained by human design.
Conventional compaction methods are classified into one-dimensional compaction and two-dimensional compaction. In the one-dimensional compaction, merely one direction, that is, the parallel direction or the vertical direction, against one side of a layout area where objects of the compaction are disposed is taken into consideration at one time. Specifically, an allocated wire is represented by using a lattice in one method of the one-dimensional compaction, and a linear space area vertical or parallel to the layout area is searched for. Such space areas are repeatedly removed so as to decrease the layout area. In another method, latitudinal or longitudinal position constraint is represented by using a graph, and an actual distance and a minimum distance between elements to be aligned are provided to branches of the graph as data. Then, the elements to be aligned are moved so that the maximum path in the graph can be shortened.
In any of the above-described methods, the movement in one direction alone is taken into consideration at one time, and hence, these methods disadvantageously cannot cope with a case where the entire compaction can be effected by moving a part of the elements to be aligned in another direction. Then, a method for coping with such a case by moving the elements in two directions at one time is proposed as the two-dimensional compaction.
In a typical example of the two-dimensional compaction, as is disclosed in "Two-Dimensional Compaction by `Zone Refining` by Hyunchul Shin, Alverto L. Sagiovanni-Vincentelli and Carlo H. Sequin", among elements disposed in a cell, a group of elements to be moved which is located at the lowest position is first moved to a further lower position. At this point, the optimal position in the horizontal direction is obtained, so that the group is two-dimensionally moved to the optimal position. A group to be moved is successively shifted to an upper group, and respective groups are repeatedly similarly moved to their lower optimal positions. By adopting this method, the problem occurring in the one-dimensional compaction can be overcome, resulting in attaining better compaction.
However, the conventional two-dimensional compaction has a problem that there is no optimal index regarding a layout position. Furthermore, since an element is simultaneously moved in the two directions, i.e., the parallel and vertical directions to the layout area, even through the layout can be optimized, wires are more frequently bent because of the change of the layout. As a result, the optimality of the layout can be spoiled, thereby disadvantageously increasing the total area. In addition, the two-dimensional compaction has another problem that it is difficult to effectively deal with wires with different widths.